/**
 * Copyright (c) 2016-present, Facebook, Inc.
 * All rights reserved.
 *
 * This source code is licensed under the BSD-style license found in the
 * LICENSE file in the root directory of this source tree. An additional grant
 * of patent rights can be found in the PATENTS file in the same directory.
 */

#include "RenameClassesV2.h"

#include <algorithm>
#include <arpa/inet.h>
#include <map>
#include <string>
#include <vector>
#include <unordered_set>
#include <unordered_map>

#include "Warning.h"
#include "Walkers.h"
#include "DexClass.h"
#include "IRInstruction.h"
#include "DexUtil.h"
#include "ReachableClasses.h"
#include "RedexResources.h"

#define MAX_DESCRIPTOR_LENGTH (1024)
#define MAX_IDENT_CHAR (62)
#define BASE MAX_IDENT_CHAR
#define MAX_IDENT (MAX_IDENT_CHAR * MAX_IDENT_CHAR * MAX_IDENT_CHAR)

static const char* METRIC_CLASSES_IN_SCOPE = "num_classes_in_scope";
static const char* METRIC_RENAMED_CLASSES = "**num_renamed**";
static const char* METRIC_FORCE_RENAMED_CLASSES = "num_force_renamed";
static const char* METRIC_REWRITTEN_CONST_STRINGS =
    "num_rewritten_const_strings";
static const char* METRIC_MISSING_HIERARCHY_TYPES =
    "num_missing_hierarchy_types";
static const char* METRIC_MISSING_HIERARCHY_CLASSES =
    "num_missing_hierarchy_classes";

static RenameClassesPassV2 s_pass;

namespace {

const char* dont_rename_reason_to_metric(DontRenameReasonCode reason) {
  switch (reason) {
    case DontRenameReasonCode::Annotated:
      return "num_dont_rename_annotated";
    case DontRenameReasonCode::Annotations:
      return "num_dont_rename_annotations";
    case DontRenameReasonCode::Specific:
      return "num_dont_rename_specific";
    case DontRenameReasonCode::Packages:
      return "num_dont_rename_packages";
    case DontRenameReasonCode::Hierarchy:
      return "num_dont_rename_hierarchy";
    case DontRenameReasonCode::Resources:
      return "num_dont_rename_resources";
    case DontRenameReasonCode::ClassNameLiterals:
      return "num_dont_rename_class_name_literals";
    case DontRenameReasonCode::Canaries:
      return "num_dont_rename_canaries";
    case DontRenameReasonCode::NativeBindings:
      return "num_dont_rename_native_bindings";
    case DontRenameReasonCode::ClassForTypesWithReflection:
      return "num_dont_rename_class_for_types_with_reflection";
    case DontRenameReasonCode::ProguardCantRename:
      return "num_dont_rename_pg_cant_rename";
    case DontRenameReasonCode::SerdeRelationships:
      return "num_dont_rename_serde_relationships";
    default:
      always_assert_log(false, "Unexpected DontRenameReasonCode: %d", reason);
  }
}

bool dont_rename_reason_to_metric_per_rule(DontRenameReasonCode reason) {
  switch (reason) {
    case DontRenameReasonCode::Annotated:
    case DontRenameReasonCode::Packages:
    case DontRenameReasonCode::Hierarchy:
      // Set to true to add more detailed metrics for renamer if needed
      return false;
    default:
      return false;
  }
}

void unpackage_private(Scope &scope) {
  walk_methods(scope,
      [&](DexMethod *method) {
        if (is_package_protected(method)) set_public(method);
      });
  walk_fields(scope,
      [&](DexField *field) {
        if (is_package_protected(field)) set_public(field);
      });
  for (auto clazz : scope) {
    if (!clazz->is_external()) {
      set_public(clazz);
    }
  }

  static DexType *dalvikinner =
    DexType::get_type("Ldalvik/annotation/InnerClass;");

  walk_annotations(scope, [&](DexAnnotation* anno) {
    if (anno->type() != dalvikinner) return;
    auto elems = anno->anno_elems();
    for (auto elem : elems) {
      // Fix access flags on all @InnerClass annotations
      if (!strcmp("accessFlags", elem.string->c_str())) {
        always_assert(elem.encoded_value->evtype() == DEVT_INT);
        elem.encoded_value->value(
            (elem.encoded_value->value() & ~VISIBILITY_MASK) | ACC_PUBLIC);
        TRACE(RENAME, 3, "Fix InnerClass accessFlags %s => %08x\n",
            elem.string->c_str(), elem.encoded_value->value());
      }
    }
  });
}

static char getident(int num) {
  assert(num >= 0 && num < BASE);
  if (num < 10) {
    return '0' + num;
  } else if (num >= 10 && num < 36){
    return 'A' + num - 10;
  } else {
    return 'a' + num - 26 - 10;
  }
}

void get_next_ident(char *out, int num) {
  int low = num;
  int mid = (num / BASE);
  int top = (mid / BASE);
  always_assert_log(num <= MAX_IDENT,
                    "Bailing, Ident %d, greater than maximum\n", num);
  if (top) {
    *out++ = getident(top);
    low -= (top * BASE * BASE);
  }
  if (mid) {
    mid -= (top * BASE);
    *out++ = getident(mid);
    low -= (mid * BASE);
  }
  *out++ = getident(low);
  *out++ = '\0';
}

static int s_base_strings_size = 0;
static int s_ren_strings_size = 0;
static int s_sequence = 0;
static int s_padding = 0;

}

void RenameClassesPassV2::build_dont_rename_resources(
    PassManager& mgr, std::set<std::string>& dont_rename_resources) {
  const Json::Value& config = mgr.get_config();
  PassConfig pc(config);
  std::string apk_dir;
  pc.get("apk_dir", "", apk_dir);

  if (apk_dir.size()) {
    // Classes present in manifest
    std::string manifest = apk_dir + std::string("/AndroidManifest.xml");
    for (std::string classname : get_manifest_classes(manifest)) {
      TRACE(RENAME, 4, "manifest: %s\n", classname.c_str());
      dont_rename_resources.insert(classname);
    }

    // Classes present in XML layouts
    for (std::string classname : get_layout_classes(apk_dir)) {
      TRACE(RENAME, 4, "xml_layout: %s\n", classname.c_str());
      dont_rename_resources.insert(classname);
    }

    // Classnames present in native libraries (lib/*/*.so)
    for (std::string classname : get_native_classes(apk_dir)) {
      auto type = DexType::get_type(classname.c_str());
      if (type == nullptr) continue;
      TRACE(RENAME, 4, "native_lib: %s\n", classname.c_str());
      dont_rename_resources.insert(classname);
    }
  }
}

void RenameClassesPassV2::build_dont_rename_class_name_literals(
    Scope& scope, std::set<std::string>& dont_rename_class_name_literals) {
  // Gather strings from const-string opcodes
  auto match = std::make_tuple(
    m::const_string(/* const-string {vX}, <any string> */)
  );

  walk_matching_opcodes(scope, match,
      [&](const DexMethod*, size_t, IRInstruction** insns){
        IRInstruction* const_string = insns[0];
        auto classname = JavaNameUtil::external_to_internal(
          const_string->get_string()->c_str());
        if (DexType::get_type(classname.c_str())) {
          TRACE(RENAME, 4,
                "Found const-string of: %s, marking %s unrenameable\n",
                const_string->get_string()->c_str(), classname.c_str());
          dont_rename_class_name_literals.insert(classname);
        }
      });
}

void RenameClassesPassV2::build_dont_rename_for_types_with_reflection(
    Scope& scope,
    const ProguardMap& pg_map,
    std::set<std::string>& dont_rename_class_for_types_with_reflection) {

    std::set<DexType*> refl_map;
    for (auto const& refl_type_str : m_dont_rename_types_with_reflection) {
      auto deobf_cls_string = pg_map.translate_class(refl_type_str);
      TRACE(RENAME, 4, "%s got translated to %s\n",
          refl_type_str.c_str(),
          deobf_cls_string.c_str());
      if (deobf_cls_string == "") {
        deobf_cls_string = refl_type_str;
      }
      DexType* type_with_refl = DexType::get_type(deobf_cls_string.c_str());
      if (type_with_refl != nullptr) {
        TRACE(RENAME, 4, "got DexType %s\n", SHOW(type_with_refl));
        refl_map.insert(type_with_refl);
      }
    }

  walk_opcodes(scope,
      [](DexMethod*) { return true; },
      [&](DexMethod* m, IRInstruction* insn) {
        if (insn->has_method()) {
          auto callee = insn->get_method();
          if (callee == nullptr || !callee->is_concrete()) return;
          auto callee_method_cls = callee->get_class();
          if (refl_map.count(callee_method_cls) == 0) return;
          std::string classname(m->get_class()->get_name()->c_str());
          TRACE(RENAME, 4,
            "Found %s with known reflection usage. marking reachable\n",
            classname.c_str());
          dont_rename_class_for_types_with_reflection.insert(classname);
        }
  });
}

void RenameClassesPassV2::build_dont_rename_canaries(
    Scope& scope,std::set<std::string>& dont_rename_canaries) {
  // Gather canaries
  for(auto clazz: scope) {
    if(strstr(clazz->get_name()->c_str(), "/Canary")) {
      dont_rename_canaries.insert(std::string(clazz->get_name()->c_str()));
    }
  }
}


void RenameClassesPassV2::build_force_rename_hierarchies(
    PassManager& mgr,
    Scope& scope,
    const ClassHierarchy& class_hierarchy,
    std::unordered_map<const DexType*, std::string>& force_rename_hierarchies) {
  std::vector<DexClass*> base_classes;
  for (const auto& base : m_force_rename_hierarchies) {
    // skip comments
    if (base.c_str()[0] == '#') continue;
    auto base_type = DexType::get_type(base.c_str());
    if (base_type != nullptr) {
      DexClass* base_class = type_class(base_type);
      if (!base_class) {
        TRACE(RENAME, 2, "Can't find class for force_rename_hierachy rule %s\n",
              base.c_str());
        mgr.incr_metric(METRIC_MISSING_HIERARCHY_CLASSES, 1);
      } else {
        base_classes.emplace_back(base_class);
      }
    } else {
      TRACE(RENAME, 2, "Can't find type for force_rename_hierachy rule %s\n",
            base.c_str());
      mgr.incr_metric(METRIC_MISSING_HIERARCHY_TYPES, 1);
    }
  }
  for (const auto& base_class : base_classes) {
    auto base_name = base_class->get_name()->c_str();
    force_rename_hierarchies[base_class->get_type()] = base_name;
    TypeSet children_and_implementors;
    get_all_children_or_implementors(
        class_hierarchy, scope, base_class, children_and_implementors);
    for (const auto& cls : children_and_implementors) {
      force_rename_hierarchies[cls] = base_name;
    }
  }
}

void RenameClassesPassV2::build_dont_rename_hierarchies(
    PassManager& mgr,
    Scope& scope,
    const ClassHierarchy& class_hierarchy,
    std::unordered_map<const DexType*, std::string>& dont_rename_hierarchies) {
  std::vector<DexClass*> base_classes;
  for (const auto& base : m_dont_rename_hierarchies) {
    // skip comments
    if (base.c_str()[0] == '#') continue;
    auto base_type = DexType::get_type(base.c_str());
    if (base_type != nullptr) {
      DexClass* base_class = type_class(base_type);
      if (!base_class) {
        TRACE(RENAME, 2, "Can't find class for dont_rename_hierachy rule %s\n",
              base.c_str());
        mgr.incr_metric(METRIC_MISSING_HIERARCHY_CLASSES, 1);
      } else {
        base_classes.emplace_back(base_class);
      }
    } else {
      TRACE(RENAME, 2, "Can't find type for dont_rename_hierachy rule %s\n",
            base.c_str());
      mgr.incr_metric(METRIC_MISSING_HIERARCHY_TYPES, 1);
    }
  }
  for (const auto& base_class : base_classes) {
    auto base_name = base_class->get_name()->c_str();
    dont_rename_hierarchies[base_class->get_type()] = base_name;
    TypeSet children_and_implementors;
    get_all_children_or_implementors(
        class_hierarchy, scope, base_class, children_and_implementors);
    for (const auto& cls : children_and_implementors) {
      dont_rename_hierarchies[cls] = base_name;
    }
  }
}

void RenameClassesPassV2::build_dont_rename_serde_relationships(
  Scope& scope,
  std::set<DexType*>& dont_rename_serde_relationships) {
  for (const auto& cls : scope) {
    const char* rawname = cls->get_name()->c_str();
    std::string name = std::string(rawname);
    name.pop_back();

    // Look for a class that matches one of the two deserializer patterns
    std::string desername = name + "$Deserializer;";
    std::replace(name.begin(), name.end(), '$', '_');
    std::string flatbuf_desername = name + "Deserializer;";

    DexType* deser = DexType::get_type(desername.c_str());
    DexType* flatbuf_deser = DexType::get_type(flatbuf_desername.c_str());
    bool has_deser_finder = false;

    if (deser || flatbuf_deser) {
      for (const auto& method : cls->get_dmethods()) {
        if (!strcmp("$$getDeserializerClass", method->get_name()->c_str())) {
          has_deser_finder = true;
          break;
        }
      }
    }

    // Look for a class that matches one of the two serializer patterns
    std::string sername = name + "$Serializer;";
    std::replace(name.begin(), name.end(), '$', '_');
    std::string flatbuf_sername = name + "Serializer;";

    DexType* ser = DexType::get_type(sername.c_str());
    DexType* flatbuf_ser = DexType::get_type(flatbuf_sername.c_str());
    bool has_ser_finder = false;

    if (ser || flatbuf_ser) {
      for (const auto& method : cls->get_dmethods()) {
        if (!strcmp("$$getSerializerClass", method->get_name()->c_str())) {
          has_ser_finder = true;
          break;
        }
      }
    }

    bool dont_rename =
      ((deser || flatbuf_deser) && !has_deser_finder) ||
      ((ser || flatbuf_ser) && !has_ser_finder);

    if (dont_rename) {
      dont_rename_serde_relationships.insert(cls->get_type());
      if (deser) dont_rename_serde_relationships.insert(deser);
      if (flatbuf_deser) dont_rename_serde_relationships.insert(flatbuf_deser);
      if (ser) dont_rename_serde_relationships.insert(ser);
      if (flatbuf_ser) dont_rename_serde_relationships.insert(flatbuf_ser);
    }
  }
}

void RenameClassesPassV2::build_dont_rename_native_bindings(
  Scope& scope,
  std::set<DexType*>& dont_rename_native_bindings) {
  // find all classes with native methods, and all types mentioned
  // in protos of native methods
  for(auto clazz: scope) {
    for (auto meth : clazz->get_dmethods()) {
      if (is_native(meth)) {
        dont_rename_native_bindings.insert(clazz->get_type());
        auto proto = meth->get_proto();
        auto rtype = proto->get_rtype();
        dont_rename_native_bindings.insert(rtype);
        for (auto ptype : proto->get_args()->get_type_list()) {
          // TODO: techincally we should recurse for array types
          // not just go one level
          if (is_array(ptype)) {
            dont_rename_native_bindings.insert(get_array_type(ptype));
          } else {
            dont_rename_native_bindings.insert(ptype);
          }
        }
      }
    }
    for (auto meth : clazz->get_vmethods()) {
      if (is_native(meth)) {
        dont_rename_native_bindings.insert(clazz->get_type());
        auto proto = meth->get_proto();
        auto rtype = proto->get_rtype();
        dont_rename_native_bindings.insert(rtype);
        for (auto ptype : proto->get_args()->get_type_list()) {
          // TODO: techincally we should recurse for array types
          // not just go one level
          if (is_array(ptype)) {
            dont_rename_native_bindings.insert(get_array_type(ptype));
          } else {
            dont_rename_native_bindings.insert(ptype);
          }
        }
      }
    }
  }
}

void RenameClassesPassV2::build_dont_rename_annotated(
    std::set<DexType*, dextypes_comparator>& dont_rename_annotated) {
  for (const auto& annotation : m_dont_rename_annotated) {
    DexType *anno = DexType::get_type(annotation.c_str());
    if (anno) {
      dont_rename_annotated.insert(anno);
    }
  }
}

class AliasMap {
  std::map<DexString*, DexString*> m_class_name_map;
  std::map<DexString*, DexString*> m_extras_map;
 public:
  void add_class_alias(DexClass* cls, DexString* alias) {
    m_class_name_map.emplace(cls->get_name(), alias);
  }
  void add_alias(DexString* original, DexString* alias) {
    m_extras_map.emplace(original, alias);
  }
  bool has(DexString* key) const {
    return m_class_name_map.count(key) || m_extras_map.count(key);
  }
  DexString* at(DexString* key) const {
    auto it = m_class_name_map.find(key);
    if (it != m_class_name_map.end()) {
      return it->second;
    }
    return m_extras_map.at(key);
  }
  const std::map<DexString*, DexString*>& get_class_map() const {
    return m_class_name_map;
  }
};

static void sanity_check(const Scope& scope, const AliasMap& aliases) {
  std::unordered_set<std::string> external_names;
  // Class.forName() expects strings of the form "foo.bar.Baz". We should be
  // very suspicious if we see these strings in the string pool that
  // correspond to the old name of a class that we have renamed...
  for (const auto& it : aliases.get_class_map()) {
    external_names.emplace(
        JavaNameUtil::internal_to_external(it.first->c_str()));
  }
  std::vector<DexString*> all_strings;
  for (auto clazz : scope) {
    clazz->gather_strings(all_strings);
  }
  sort_unique(all_strings);
  int sketchy_strings = 0;
  for (auto s : all_strings) {
    if (external_names.find(s->c_str()) != external_names.end() ||
        aliases.has(s)) {
      TRACE(RENAME, 2, "Found %s in string pool after renaming\n", s->c_str());
      sketchy_strings++;
    }
  }
  if (sketchy_strings > 0) {
    fprintf(stderr,
            "WARNING: Found a number of sketchy class-like strings after class "
            "renaming. Re-run with TRACE=RENAME:2 for more details.");
  }
}


void RenameClassesPassV2::eval_classes(
    Scope& scope,
    const ClassHierarchy& class_hierarchy,
    ConfigFiles& cfg,
    bool rename_annotations,
    PassManager& mgr) {
  std::unordered_map<const DexType*, std::string> force_rename_hierarchies;
  std::set<std::string> dont_rename_class_name_literals;
  std::set<std::string> dont_rename_class_for_types_with_reflection;
  std::set<std::string> dont_rename_canaries;
  std::set<std::string> dont_rename_resources;
  std::unordered_map<const DexType*, std::string> dont_rename_hierarchies;
  std::set<DexType*> dont_rename_native_bindings;
  std::set<DexType*> dont_rename_serde_relationships;
  std::set<DexType*, dextypes_comparator> dont_rename_annotated;

  build_force_rename_hierarchies(
      mgr, scope, class_hierarchy, force_rename_hierarchies);

  build_dont_rename_serde_relationships(scope, dont_rename_serde_relationships);
  build_dont_rename_resources(mgr, dont_rename_resources);
  build_dont_rename_class_name_literals(scope, dont_rename_class_name_literals);
  build_dont_rename_for_types_with_reflection(scope, cfg.get_proguard_map(),
    dont_rename_class_for_types_with_reflection);
  build_dont_rename_canaries(scope, dont_rename_canaries);
  build_dont_rename_hierarchies(
      mgr, scope, class_hierarchy, dont_rename_hierarchies);
  build_dont_rename_native_bindings(scope, dont_rename_native_bindings);
  build_dont_rename_annotated(dont_rename_annotated);

  std::string norule = "";

  for(auto clazz: scope) {
    // Short circuit force renames
    if (force_rename_hierarchies.count(clazz->get_type()) > 0) {
      m_force_rename_classes.insert(clazz);
      continue;
    }

    // Don't rename annotations
    if (!rename_annotations && is_annotation(clazz)) {
      m_dont_rename_reasons[clazz] =
          { DontRenameReasonCode::Annotations, norule };
      continue;
    }

    // Don't rename types annotated with anything in dont_rename_annotated
    bool annotated = false;
    for (const auto& anno : dont_rename_annotated) {
      if (has_anno(clazz, anno)) {
        m_dont_rename_reasons[clazz] =
            { DontRenameReasonCode::Annotated, std::string(anno->c_str()) };
        annotated = true;
        break;
      }
    }
    if (annotated) continue;

    const char* clsname = clazz->get_name()->c_str();
    std::string strname = std::string(clsname);

    // Don't rename anything mentioned in resources
    if (dont_rename_resources.count(clsname) > 0) {
      m_dont_rename_reasons[clazz] =
          { DontRenameReasonCode::Resources, norule };
      continue;
    }

    // Don't rename anythings in the direct name blacklist (hierarchy ignored)
    if (m_dont_rename_specific.count(clsname) > 0) {
      m_dont_rename_reasons[clazz] =
          { DontRenameReasonCode::Specific, strname };
      continue;
    }

    // Don't rename anything if it falls in a blacklisted package
    bool package_blacklisted = false;
    for (const auto& pkg : m_dont_rename_packages) {
      if (strname.rfind("L"+pkg) == 0) {
        TRACE(RENAME, 2, "%s blacklisted by pkg rule %s\n",
            clsname, pkg.c_str());
        m_dont_rename_reasons[clazz] = { DontRenameReasonCode::Packages, pkg };
        package_blacklisted = true;
        break;
      }
    }
    if (package_blacklisted) continue;

    if (dont_rename_class_name_literals.count(clsname) > 0) {
      m_dont_rename_reasons[clazz] =
          { DontRenameReasonCode::ClassNameLiterals, norule };
      continue;
    }

    if (dont_rename_class_for_types_with_reflection.count(clsname) > 0) {
      m_dont_rename_reasons[clazz] =
          { DontRenameReasonCode::ClassForTypesWithReflection, norule };
      continue;
    }

    if (dont_rename_canaries.count(clsname) > 0) {
      m_dont_rename_reasons[clazz] = { DontRenameReasonCode::Canaries, norule };
      continue;
    }

    if (dont_rename_native_bindings.count(clazz->get_type()) > 0) {
      m_dont_rename_reasons[clazz] =
          { DontRenameReasonCode::NativeBindings, norule };
      continue;
    }

    if (dont_rename_hierarchies.count(clazz->get_type()) > 0) {
      std::string rule = dont_rename_hierarchies[clazz->get_type()];
      m_dont_rename_reasons[clazz] = { DontRenameReasonCode::Hierarchy, rule };
      continue;
    }

    if (dont_rename_serde_relationships.count(clazz->get_type()) > 0) {
      m_dont_rename_reasons[clazz] =
          { DontRenameReasonCode::SerdeRelationships, norule };
      continue;
    }

    if (!can_rename_if_ignoring_blanket_keep(clazz)) {
      m_dont_rename_reasons[clazz] =
          { DontRenameReasonCode::ProguardCantRename, norule };
      continue;
    }
  }
}

void RenameClassesPassV2::eval_pass(DexStoresVector& stores,
                                    ConfigFiles& cfg,
                                    PassManager& mgr) {
  auto scope = build_class_scope(stores);
  ClassHierarchy class_hierarchy = build_type_hierarchy(scope);
  eval_classes(scope, class_hierarchy, cfg, m_rename_annotations, mgr);
}

void RenameClassesPassV2::rename_classes(
    Scope& scope,
    ConfigFiles& cfg,
    bool rename_annotations,
    PassManager& mgr) {
  // Make everything public
  unpackage_private(scope);

  AliasMap aliases;
  for(auto clazz: scope) {
    auto dtype = clazz->get_type();
    auto oldname = dtype->get_name();

    if (m_force_rename_classes.count(clazz) > 0) {
      mgr.incr_metric(METRIC_FORCE_RENAMED_CLASSES, 1);
      TRACE(RENAME, 2, "Forced renamed: '%s'\n", oldname->c_str());
    } else if (m_dont_rename_reasons.find(clazz) !=
          m_dont_rename_reasons.end()) {
      auto reason = m_dont_rename_reasons[clazz];
      std::string metric = dont_rename_reason_to_metric(reason.code);
      mgr.incr_metric(metric, 1);
      if (dont_rename_reason_to_metric_per_rule(reason.code)) {
        std::string str = metric + "::" + std::string(reason.rule);
        mgr.incr_metric(str, 1);
        TRACE(RENAME, 2, "'%s' NOT RENAMED due to %s'\n",
            oldname->c_str(), str.c_str());
      } else {
        TRACE(RENAME, 2, "'%s' NOT RENAMED due to %s'\n",
            oldname->c_str(), metric.c_str());
      }
      continue;
    }

    mgr.incr_metric(METRIC_RENAMED_CLASSES, 1);

    char clzname[4];
    const char* padding = "0000000000000";
    get_next_ident(clzname, s_sequence);
    // The X helps our hacked Dalvik classloader recognize that a
    // class name is the output of the redex renamer and thus will
    // never be found in the Android platform.
    char descriptor[MAX_DESCRIPTOR_LENGTH];
    always_assert((s_padding + strlen("LX/;") + 1) < MAX_DESCRIPTOR_LENGTH);
    sprintf(descriptor, "LX/%.*s%s;",
        (s_padding < (int)strlen(clzname)) ? 0 :
            s_padding - (int)strlen(clzname),
        padding,
        clzname);
    s_sequence++;

    auto exists = DexString::get_string(descriptor);
    always_assert_log(
        !exists, "Collision on class %s (%s)", oldname->c_str(), descriptor);

    auto dstring = DexString::make_string(descriptor);
    aliases.add_class_alias(clazz, dstring);
    dtype->assign_name_alias(dstring);
    std::string old_str(oldname->c_str());
    std::string new_str(descriptor);
//    proguard_map.update_class_mapping(old_str, new_str);
    s_base_strings_size += strlen(oldname->c_str());
    s_ren_strings_size += strlen(dstring->c_str());

    TRACE(RENAME, 2, "'%s' ->  %s'\n", oldname->c_str(), descriptor);
    while (1) {
     std::string arrayop("[");
      arrayop += oldname->c_str();
      oldname = DexString::get_string(arrayop.c_str());
      if (oldname == nullptr) {
        break;
      }
      auto arraytype = DexType::get_type(oldname);
      if (arraytype == nullptr) {
        break;
      }
      std::string newarraytype("[");
      newarraytype += dstring->c_str();
      dstring = DexString::make_string(newarraytype.c_str());

      aliases.add_alias(oldname, dstring);
      arraytype->assign_name_alias(dstring);
    }
  }


  /* Now rewrite all const-string strings for force renamed classes. */
  auto match = std::make_tuple(
    m::const_string()
  );

  walk_matching_opcodes(scope, match,
      [&](const DexMethod*, size_t, IRInstruction** insns){
        IRInstruction* insn = insns[0];
        DexString* str = insn->get_string();
        // get_string instead of make_string here because if the string doesn't
        // already exist, then there's no way it can match a class
        // that was renamed
        DexString* internal_str = DexString::get_string(
          JavaNameUtil::external_to_internal(str->c_str()).c_str());
        // Look up both str and intternal_str in the map; maybe str was
        // internal to begin with?
        DexString* alias_from = nullptr;
        DexString* alias_to = nullptr;
        if (aliases.has(internal_str)) {
          alias_from = internal_str;
          alias_to = aliases.at(internal_str);
          // Since we matched on external form, we need to map internal alias
          // back.
          // make_string here because the external form of the name may not be
          // present in the string table
          alias_to = DexString::make_string(
            JavaNameUtil::internal_to_external(std::string(alias_to->c_str())));
        } else if (aliases.has(str)) {
          alias_from = str;
          alias_to = aliases.at(str);
        }
        if (alias_to) {
          DexType* alias_from_type = DexType::get_type(alias_from);
          DexClass* alias_from_cls = type_class(alias_from_type);
          if (m_force_rename_classes.count(alias_from_cls) > 0) {
            mgr.incr_metric(METRIC_REWRITTEN_CONST_STRINGS, 1);
            insn->set_string(alias_to);
            TRACE(RENAME, 3, "Rewrote const-string \"%s\" to \"%s\"\n",
                str->c_str(), alias_to->c_str());
          }
        }
      });

  /* Now we need to re-write the Signature annotations.  They use
   * Strings rather than Type's, so they have to be explicitly
   * handled.
   */

  /* In Signature annotations, parameterized types of the form Foo<Bar> get
   * represented as the strings
   *   "Lcom/baz/Foo" "<" "Lcom/baz/Bar;" ">"
   *
   * Note that "Lcom/baz/Foo" lacks a trailing semicolon.
   * So, we have to alias those strings if they exist. Signature annotations
   * suck.
   */
  for (const auto& apair : aliases.get_class_map()) {
    char buf[MAX_DESCRIPTOR_LENGTH];
    const char *sourcestr = apair.first->c_str();
    size_t sourcelen = strlen(sourcestr);
    if (sourcestr[sourcelen - 1] != ';') continue;
    strcpy(buf, sourcestr);
    buf[sourcelen - 1] = '\0';
    auto dstring = DexString::get_string(buf);
    if (dstring == nullptr) continue;
    strcpy(buf, apair.second->c_str());
    buf[strlen(apair.second->c_str()) - 1] = '\0';
    auto target = DexString::make_string(buf);
    aliases.add_alias(dstring, target);
  }
  static DexType *dalviksig =
    DexType::get_type("Ldalvik/annotation/Signature;");
  walk_annotations(scope, [&](DexAnnotation* anno) {
    if (anno->type() != dalviksig) return;
    auto elems = anno->anno_elems();
    for (auto elem : elems) {
      auto ev = elem.encoded_value;
      if (ev->evtype() != DEVT_ARRAY) continue;
      auto arrayev = static_cast<DexEncodedValueArray*>(ev);
      auto const& evs = arrayev->evalues();
      for (auto strev : *evs) {
        if (strev->evtype() != DEVT_STRING) continue;
        auto stringev = static_cast<DexEncodedValueString*>(strev);
        if (aliases.has(stringev->string())) {
          TRACE(RENAME, 5, "Rewriting Signature from '%s' to '%s'\n",
              stringev->string()->c_str(),
              aliases.at(stringev->string())->c_str());
          stringev->string(aliases.at(stringev->string()));
        }
      }
    }
  });

  for (auto* clazz : scope) {
    clazz->sort_methods();
    clazz->sort_fields();
  }

  sanity_check(scope, aliases);
}

void RenameClassesPassV2::run_pass(DexStoresVector& stores,
                                   ConfigFiles& cfg,
                                   PassManager& mgr) {
  if (mgr.no_proguard_rules()) {
    TRACE(RENAME, 1,
          "RenameClassesPassV2 not run because no ProGuard configuration was "
          "provided.");
    return;
  }
  auto scope = build_class_scope(stores);
  int total_classes = scope.size();

  s_base_strings_size = 0;
  s_ren_strings_size = 0;
  s_sequence = 0;
  // encode the whole sequence as base 62, [0 - 9 + a - z + A - Z]
  s_padding = std::ceil(std::log(total_classes) / std::log(BASE));

  rename_classes(scope, cfg, m_rename_annotations, mgr);

  mgr.incr_metric(METRIC_CLASSES_IN_SCOPE, total_classes);

  TRACE(RENAME, 1,
      "Total classes in scope for renaming: %d chosen padding: %d\n",
      total_classes, s_padding);
  TRACE(RENAME, 1, "String savings, at least %d-%d = %d bytes \n",
      s_base_strings_size, s_ren_strings_size,
      s_base_strings_size - s_ren_strings_size);
}
